package com.zhugang.week14.coding;

/**
 * @program algorithms
 * @description: reverseList
 * @author: chanzhugang
 * @create: 2022/10/25 09:39
 */
public class ReverseList {

    /**
     * 剑指offer 24 反转链表
     * https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        // 每次遍历节点,让next指向前一个节点
        ListNode newNode = null;
        ListNode p = head;
        while (p != null) {
            ListNode next = p.next;
            p.next = newNode;
            newNode = p;
            p = next;
        }
        return newNode;
    }

    public ListNode reverseList2(ListNode head) {
        // 递归写法
        if (head == null || head.next == null) {
            // 递归终止条件
            return head;
        }
        // 递的过程
        ListNode node = reverseList2(head.next);
        // 归的处理
        head.next.next = head;
        head.next = null;
        return node;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}